#include <iostream>
#include <vector>
#include <sstream>
#include <fstream>
#include <cmath>
#include <cstdlib>

#include <algorithm>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <string.h>
#include <map>
#include <set>
#include <stack>

using namespace std;


template<typename T>
T* mallocArray(int n) {
	T* arr = (T*)malloc(n * sizeof(T));
	return arr;
}
template<typename T>
void freeArray(T* arr) {
	if(arr != NULL){
        free(arr);
	}
}


typedef struct LinkNode{
	int index;
	LinkNode* next = NULL;
}LinkNode;

typedef struct Node{
	unsigned int data;
	LinkNode* first_neighbor = NULL;
}Node;

typedef struct Grap{
	int node_num;
	Node* nodes;
}Grap;


string testFile = "data/test_data1.txt";//30000 node,1004812
//string testFile = "data/test_data2.txt";//25700 node,2896262
//string testFile = "data/test_data3.txt";


string resultFile = "result.txt";

Grap grap;
int max_record_num = 300000;
int* visited = NULL;
int* first = NULL;
int* back = NULL;
typedef vector<int> Loop; //环
typedef set<Loop> Loops; //环的集合
Loops all_loops;
Loops loops3, loops4, loops5, loops6, loops7;
Loops new_loops;//新生成的环集合
vector<int> pathS;
stack<int> vexS;//路径堆栈
vector<set<Loop>> nodeCir(max_record_num);//每个顶点所在环的引用集合
int order; //定点遍历序号

inline unsigned int parse(char** s){
	char *p = *s;
	unsigned int val = *(p++) - '0';
	while(*p != ','){
		val = 10*val + *(p++) - '0';
	}
	*s = p;
	return val;
}
void loadData_and_createGrap(){
	int fd = open(testFile.c_str(), O_RDONLY);
    int file_size = lseek(fd, 0, SEEK_END);
    char* p_map =(char*)mmap(NULL, file_size, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);
	
	char *p = p_map;
	unsigned int a1, a2; //每行数据中的两个账户
	grap.nodes = mallocArray<Node>(max_record_num);//图中的总节点数不会超过max_record_num
	Node* nodes = grap.nodes;
	int node_num = 0;
	map<unsigned int, int> mapSite; //记录账户节点在数组中的位置
	LinkNode* neighbor, *q;
	int i, j;
	while(*p != '\0'){
		a1 = parse(&p);//或得该行数据中的第一个账户信息
		p++;
		a2 = parse(&p);//或得该行数据中的第二个账户信息
		i = mapSite[a1];//返回该账户在节点数组中的位置，若还没有在节点数组中，则默认返回0(map默认就是返回0)
		j = mapSite[a2];
		switch(i==0){
			case 1:
				mapSite[a1] = ++node_num;
				i = node_num-1;
				nodes[i].first_neighbor = NULL;
				nodes[i].data = a1;
				break;
			case 0:
				i--;
		}
		switch(j==0){
			case 1:
				mapSite[a2] = ++node_num;
				j = node_num-1;
				nodes[j].first_neighbor = NULL;
				nodes[j].data = a2;
				break;
			case 0:
				j--;
		}
		neighbor = (LinkNode*) malloc(sizeof(LinkNode));
		neighbor->index = j;
		neighbor->next = NULL;
		switch(nodes[i].first_neighbor == NULL){
			case 1:
				nodes[i].first_neighbor = neighbor;
				break;
			case 0:
				q = nodes[i].first_neighbor;
				while(q->next != NULL) q = q->next;
				q->next = neighbor;
		}
		
		while(*p != '\n'){p++;}
		p++;
	}
	grap.node_num = node_num;
	munmap(p_map, file_size);
}

void free_grap(Grap* g){
	Node* nodes = g->nodes;
	int node_num = g->node_num;
	LinkNode *p, *q;
	//释放为邻接链表分配的内存空间
	for(int i=0; i < node_num; i++){
		p = nodes[i].first_neighbor;
		while(p != NULL){
			q = p->next;
			free(p);
			p = q;
		}
	}
	//释放为图中的节点分配的内存
	freeArray(nodes);
}
void printGrap(Grap* g){
	Node* nodes = g->nodes;
	LinkNode* p;
	for(int i=0; i<g->node_num; i++){
		cout<<nodes[i].data<<" ";
		p = nodes[i].first_neighbor;
		while(p != NULL){
			cout<<nodes[p->index].data<<" ";
			p = p->next;
		}
		cout<<endl<<endl;
	}
}
void printLoop(const Loop& loop){
	for(uint x : loop) cout<<x<<" ";
	cout<<endl;
}
void printLoops(const Loops& loops){
	for(auto &loop : loops){
		for(auto x : loop) cout<<x<<" ";
		cout<<endl;
	}
}

Loop subPath(const vector<int> &path, int w){
	Loop lp;
	int i = 0;
	while(path[i] != w) ++i;
	while(i<path.size()) lp.push_back(path[i++]);
	return lp;
}

void getCrossLoops(int w){
	int z;
	for(auto& each_loop:nodeCir[w]){
		z = each_loop[0];
		if(visited[z] == 1){
			Loop lp1 = subPath(pathS, z);
			Loop lp2 = subPath(each_loop, w);
			lp1.insert(lp1.end(), lp2.begin(), lp2.end());
			if(lp1.size()<8 && lp1.size()>2) all_loops.insert(lp1);
			new_loops.insert(lp1);
		}else{
			nodeCir[w].erase(each_loop);
		}
	}
}

void getSimLoops(Grap* g, int v){
	Node* nodes = g->nodes;
	LinkNode* p;
	int neighbor;
	pathS.push_back(v);//压v入路径堆栈
	visited[v] = 1;//设置入栈标志,表示该顶点正在路径堆栈中被遍历
	first[v] = back[v] = order;
	set<int> unSet;//定义未遍历邻居节点集合
	for(p=nodes[v].first_neighbor; p!=NULL; p=p->next){
		neighbor = p->index;
		if(visited[neighbor] > 0){//该邻居已遍历过
			//该邻居在当前路径堆栈pathS中,直接形成简单回路
			if(visited[neighbor] == 1){
				Loop lp = subPath(pathS, neighbor);
				if(lp.size()<8 && lp.size()>2) all_loops.insert(lp);
				new_loops.insert(lp);
			}else{//间接形成简单回路
				getCrossLoops(neighbor);
			}
			if(back[neighbor] < back[v]) back[v]=back[neighbor];
		}else{//记录未遍历邻居节点
			unSet.insert(neighbor);
		}
	}
	//处理未访问邻居节点，即unSet中的节点
	for(int neighbor : unSet){
		if(visited[neighbor] == 0){
			order++;
			getSimLoops(g, neighbor);
		}else{
			getCrossLoops(neighbor);
		}
		if(back[neighbor] < back[v]) back[v]=back[neighbor];
	}
	visited[v] = 2; //设置该顶点已遍历完成
	for(Loop each_loop : new_loops){
		for(int &val : each_loop){
			nodeCir[val].insert(each_loop);
		}
	}
	new_loops.clear();
	
	
	pathS.pop_back(); //将v弹出路径堆栈pathS
	vexS.push(v); //压v入强连通分量堆栈
	if(back[v] >= first[v]){//强连通分量
		while(!vexS.empty()){
			int z = vexS.top();
			nodeCir[z].clear();
			vexS.pop();
		}
	}
}

void findSimLoops(Grap* g){
	int node_num = g->node_num;
	Node* nodes = g->nodes;
	for(int i=0; i<node_num; i++){
		visited[i] = 0;
		first[i] = 0;
		back[i] = 0;
	}
	order = 1;
	for(int i=0; i<node_num; i++){
		if(visited[i] == 0){
			getSimLoops(g, i);
		}
	}
}

int main(int argc, char* argv[]){
	
	clock_t startTime = clock();
	loadData_and_createGrap();
	clock_t endTime = clock();
	cout << "LoadData: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	
	visited = mallocArray<int>(grap.node_num);
	first = mallocArray<int>(grap.node_num);
	back = mallocArray<int>(grap.node_num);
	
	startTime = clock();
	findSimLoops(&grap);
	endTime = clock();
	cout << "findSimLoops: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	cout<<"all_loops.size = "<<all_loops.size()<<endl;
	
	freeArray(visited);
	freeArray(first);
	freeArray(back);
	free_grap(&grap);
	return 0;
}